#include "Bitree_Fun.h"

int create_Bitree(Bitree &T,int number){//创建二叉树                    


    if(T==NULL){
        T=(Bitree)malloc(sizeof(node));
        T->data=number;
        T->lchild=T->rchild=NULL;
        return 1;
    }else if(number==T->data){
        return 0;
   	}else if(number<T->data){
        return create_Bitree(T->lchild,number);
    } else{
       return create_Bitree(T->rchild,number);
    }
     
}



void front_traversal(Bitree T){//前序遍历

	if(T==NULL){
		return;
	}
	printf("%d->",T->data);
	front_traversal(T->lchild );
	front_traversal(T->rchild );
}

void mid_traversal(Bitree T){//中序遍历
	
	if(T==NULL){
		return;
	}
	mid_traversal(T->lchild );
	printf("%d->",T->data);	
	mid_traversal(T->rchild );
	
}

void rear_traversal(Bitree T){//后序遍历
	
	if(T==NULL){
		return;
	}
	rear_traversal(T->lchild );
	rear_traversal(T->rchild );
	printf("%d->",T->data);	
	
}

void sequence_traversal(Bitree T,queue front,queue rear){//层序遍历(使用队列)
	
	push(front,rear,T);
	while(front->next!=rear){              //当队列非空时，检查队头元素，
		Bitree s1=front->next->tree_data;  //若左右子树非空，将子树入队
		if(s1->lchild!=NULL){              //将队头元素出队
			push(front,rear,s1->lchild);
		}
		if(s1->rchild!=NULL){
			push(front,rear,s1->rchild);
		}
		printf("%d->",s1->data);
		pop(front,rear);
		
	}
	return;
}
 
    
void find_Bitree(Bitree T, int number){//按值查找
	
	
	if(T==NULL){
        printf("no find\n");
        return ;
    }else if(number==T->data){
    	printf("successfully find\n");
        return ;
   	}else if(number<T->data){
        return find_Bitree(T->lchild,number);
    } else{
       return find_Bitree(T->rchild,number);
    }
	
}

void delete_Bitree(Bitree T,Bitree s){//删除结点
	      if(s->lchild==NULL&&s->rchild==NULL){//结点无子树
	        if(T->lchild->data==s->data ){
	        	free(s);
		        T->lchild =NULL;
			}else{
				free(s);
		        T->rchild =NULL;
			}
		    
		    
		    
	}else if(s->lchild==NULL){//有右子树
		    if(T->lchild->data==s->data ){
		    	T->lchild =s->rchild;
	        	free(s);
		        
			}else{
				T->rchild =s->rchild ;
				free(s);
		       
			}	
		
	}else if(s->rchild==NULL){//有左子树
		    if(T->lchild->data==s->data ){
		    	T->lchild =s->lchild;
	        	free(s);
		        
			}else{
				T->rchild =s->lchild ;
				free(s);
		       
			}	
		   
		   
	
    }else{//有左右子树
    	    Bitree s1=s->lchild;
    	    while(s1->rchild!=NULL){
    	    	 s1=s1->rchild;
			}
			s->data=s1->data;
			delete_find_Bitree(s->lchild ,s1->data);
    	
	}
	
}

void delete_find_Bitree(Bitree T, int number){//删除过程中的查找
	
	if(T==NULL){
        printf("ERROR\n");
        return;
    }else if(T->lchild!=NULL&&T->lchild->data==number){
    	Bitree s;
    	s=T->lchild; 
    	delete_Bitree(T,s);
        return ;
        
   	}else if(T->lchild!=NULL&&T->lchild->data==number){
   			Bitree s;
   		delete_Bitree(T,s);
        return ;
	
	}else if(number<T->data){
        return delete_find_Bitree(T->lchild,number);
    } else{
       return delete_find_Bitree(T->rchild,number);
    }
	
	
}

void push(queue front,queue rear,Bitree T){	//入队
	if(front->next==rear ){
		queue s;
		s=(pnode*)malloc(sizeof(pnode));
		s->tree_data =T;
		front->next=s;
	    rear->next=s;
	    s->next=rear;
	    
		
	}else{
		queue s;
		s=(pnode*)malloc(sizeof(pnode));
		s->tree_data  =T;
		rear->next->next=s;
    	rear->next=s;
    	s->next=rear;
	}
	
	
	
}

void pop(queue front,queue rear){//出队
	if(front->next==rear){
		return;
	}else{
		queue s1;
		s1=front->next;
		front->next=s1->next;
		if(front->next==rear){
			rear->next=front;
		}
		free(s1);
		
	}
	return;
	
}

void menu(){//菜单 
	printf("**********************************\n");
	printf("***         Bitree             ***\n");
	printf("***     1.Create_Bitree        ***\n");
	printf("***     2.traversal_Bitree     ***\n");
	printf("***     3.find_Bitree          ***\n");
	printf("***     4.delete_Bitree        ***\n");
	printf("***     0.exit                 ***\n");
	printf("**********************************\n");
	printf("\n\n");
}